package foreignTrip38;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

public class UserMainCode
{
	public static String output1;

	public static void foreign_trip(int input1, String input2)
	{
		Map<String, List<String>> edges = new HashMap<String, List<String>>();
		String[] pairs = input2.substring(2, input2.length() - 2).split("\\),\\(");
		for(String pair : pairs) {
			String[] edge = pair.split(",");
			List<String> l = edges.get(edge[0]);
			if(l == null) {
				l = new ArrayList<String>();
				edges.put(edge[0], l);
			}
			l.add(edge[1]);
			l = edges.get(edge[1]);
			if(l == null) {
				l = new ArrayList<String>();
				edges.put(edge[1], l);
			}
			l.add(edge[0]);
		}
		Set<String> set[] = new Set[2];
		set[0] = new HashSet<String>();
		set[1] = new HashSet<String>();
		for(String key : edges.keySet()) {
			if(set[0].contains(key) || set[1].contains(key))
				continue;
			set[0].add(key);
			Queue<String> q = new LinkedList<String>();
			q.add(key);
			while(!q.isEmpty()) {
				String node = q.poll();
				int curset = 1;
				if(!set[1].contains(node))
					curset = 0;
				int nextset = (curset + 1) % 2;
				for(String val : edges.get(node)) {
					if(set[curset].contains(val)) {
						output1 = "no";
						System.out.println(set[0]);
						System.out.println(set[1]);
						return;
					}
					if(set[nextset].add(val))
						q.add(val);
				}
			}
		}
		output1 = "yes";
		System.out.println(set[0]);
		System.out.println(set[1]);
	}
	public static void main(String[] args) {
		foreign_trip(4, "{(1,2),(2,3),(3,4),(5,6)}");
		System.out.println(output1);
		foreign_trip(3, "{(1,2),(1,3),(4,5),(2,3)}");
		System.out.println(output1);
	}
}
